Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Als erstes eine Ansage. Heute in einer Woche fängt die Vorlesung eine dreiviertel Stunde später an,

weil da ist diese Vorstellungsveranstaltung und wo die mich praktischerweise genau während meiner Vorlesung gebucht haben

und das nicht ändern wollten. Deswegen fangen wir da erst um 5 Uhr an.

Entsprechend längere Zeit?

Können wir machen. Ich bin nicht davon ausgegangen, dass...

In Interesse Ihres sicheren Heimwegs werde ich jetzt mal sagen, ne, wir machen nicht lange.

Ich glaube die Zeit haben wir wohl.

Genau, noch eine Ansage ist, wir machen ja, wir haben ja letztes Mal als ich nicht da war, angefangen mit Spiele KI

und werden das heute weitermachen und wir wollen vor Weihnachten, also in dieser Woche zwischen dem 8. und was immer 8 plus 7 ist,

da wollen wir ein Cala-Turnier machen. Cala ist eines der ältesten Spiele, die wir kennen.

Das ist trotzdem relativ spannend und das ist gerade schwer genug, dass man es nicht ganz so in einem Nachmittag lösen kann.

Das ist im Prinzip auch parametrisch genug und die Idee ist, dass wir ein Turnier ausrufen, wo sie in Gruppen Cala-KIs bauen können

und die wir dann gegeneinander antreten lassen. Und dass wir da irgendwie ein großes Happening machen und dann gucken, wer es am besten kann.

Und natürlich, das haben wir letztes Semester auch gemacht und wenn alles gut geht, kriegen wir die Einträge vom letzten Jahr auch noch zum Laufen

und dann können wir mal sehen, ob sie es besser können als die vom letzten Jahr. Aber das ist nicht versprochen.

Und für alle, die immer noch mit Prolog rumquengeln, das kann man in der Programmiersprache machen, die man gerne möchte.

Ich glaube, verbinden kann man aber vielleicht nur, wenn es in Java ist. Das weiß ich nicht mehr.

Das werden wir aber dann genauestens bekannt geben. Ich wollte Sie nur schonmal warnen, dass so etwas kommt.

Gut, irgendwelche Fragen, bevor wir jetzt anfangen.

Okay, letztes Mal steckten wir noch tief in der Suche. Ich glaube, dieses hier war die erste Slide, mit der da angefangen wurde.

Die hat einen A-Stern gerade behandelt und ich hoffe, Sie haben sich alle so ein bisschen hier mitgespielt, um zu sehen, wie sich A-Stern tatsächlich unter verschiedensten Heuristiken verhält.

Es gibt mir, ich fand das immer ganz gut, wenn man da so ein Gefühl dafür kriegt, was exponentiell heißt in der Suche.

Die Pfade ist nie länger als so, aber man hat so das Gefühl, die nächste Stunde kann man irgendwie voraussehen, was er da macht.

Gut. Das nächste Thema war sozusagen, wir haben gesehen hiermit, wo sind selbst für A-Stern, im besten unsere Algorithmen, wo sind da die Grenzen?

Und sehr häufig sind die Probleme in der Praxis eher schwieriger.

Und manchmal ist es so, dass uns eigentlich gar nicht der Lösungsweg interessiert, sondern einfach nur so eine Konfiguration.

In solchen Fällen kann man etwas machen, was lokale Suche heißt. Da gibt man dann sehr viel auf. Man gibt alle solche Sachen wie Systematizität und alles und Krempel gibt man auf.

Aber man kann trotzdem noch etwas rauskriegen. Das typische Beispiel, ein typisches Beispiel sind so Konfigurationsprobleme wie das Achdam-Problem, klassisches altes Problem.

Und da guckt man sich im Suchalgorithmus nur den momentanen Zustand an.

Das heißt insbesondere, dass man nicht weiß, ob man an diesem Zustand schon mal war.

Aber man hat einen Algorithmus, der irgendwie in konstanter Zeit läuft.

Ja, typisches anderes Problem ist das Traveling Salesman Problem, haben Sie sicherlich auch schon von gehört.

Und die Idee bei diesen Dingern ist, dass man mit irgendeiner randomisierten Einstiegsstelle anfängt und dass man dann tatsächlich immer Greedy der Nase nachgeht.

Nicht wie in A-Stern, dass man immer irgendwie versucht Backtracking zu machen, sondern einfach immer nur vorwärts läuft.

Da ist der Algorithmus. Und das Problem an der Sache ist klar, man weiß nie, ob man in einem lokalen Maximum ist.

Die Idee ist, dass man immer dem steilsten Anstieg im Zustandsraum nachläuft.

Und wenn man das von hier aus tut, dann landet man in einem lokalen Maximum. Und die Frage ist, was macht man dann?

Aber die Situation ist noch viel schlimmer. Man hat flache Strecken, da weiß man nicht, soll ich nach links gehen oder nach rechts, weil man ja immer versucht hochzukommen.

Man weiß nicht, ist man auf einem flachen lokalen Maximum, dem man gerne entkommen möchte, oder ist man auf einer Art Schulter,

wo man eigentlich immer nur weiterlaufen müsste, bis man dann ins globale Maximum geht.

Weiß man nicht, warum nicht? Weil man sich nichts merkt als Algorithmus.

Das ist im Wesentlichen so, als ob man irgendwie versucht den Mount Everest zu bestreiten, von Erlangen aus.

Und es ist außer dem Nebel, das heißt, man sieht überhaupt nicht, wo man ist. Und zweitens hat man noch Gedächtnisverlust.

Man kann sich ja nichts mehr erinnern. Das ist sozusagen das Problem. Und wie geht man da mit um?

Aber natürlich ist das Problem immer noch viel schlimmer, als man so denkt, wenn ich Ihnen so ein Bild zeige.

Das ist relativ einfach. Aber typischerweise sind die Räume eben nicht nur eindimensional, sondern die sind vieldimensional.

Das heißt, wenn wir hier irgendwie so eine Schulter, dem könnte man ja vielleicht noch entkommen.

Aber typischerweise sind diese Räume sehr viel höherdimensional. Ich habe hier jetzt versucht, einen dreidimensionalen Raum aufzuzeigen.

Und das ist eine typische Konfiguration, wo man solche Bergrücken hat, die ganz viele kleine lokale Maxima haben.